import tool.TreeNode;

/**
 * 返回与给定前序遍历preorder 相匹配的二叉搜索树（binary search tree）的根结点。
 * (回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于node.left的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，前序遍历首先显示节点node 的值，然后遍历 node.left，接着遍历 node.right。）
 * 题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。
 * <p>
 * 示例：
 * 输入：[8,5,1,7,10,12]
 * 输出：[8,5,10,1,7,null,12]
 * <p>
 * 提示：
 * 1 <= preorder.length <= 100
 * 1 <= preorder[i]<= 10^8
 * preorder 中的值互不相同
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q01008m {

    public TreeNode bstFromPreorder(int[] preorder) {
        return build(preorder, 0, preorder.length - 1);
    }

    public TreeNode build(int[] preorder, int start, int end) {
        if (start > end) return null;
        TreeNode root = new TreeNode(preorder[start]);
        int rr = start + 1; // 右子树的根的下标（若没有右子树，值为end+1）
        while (rr <= end) {
            if (preorder[rr] > preorder[start]) { // 找到右子树的根节点
                break;
            }
            rr++;
        }
        root.left = build(preorder, start + 1, rr - 1); // 递归构造左子树
        root.right = build(preorder, rr, end); // 递归构造右子树
        return root;
    }
}
